package com.it.zhangjun.arithmetic.队列;

import java.util.*;

/**
 * @author zhangj
 * @description 二叉树的层次遍历
 * @date 2021-03-25 11:28
 */
public class LT_二叉树的层次遍历 {
    public static void main(String[] args) {
        TreeNode treeNode6 = new TreeNode(null, 6, null);
        TreeNode treeNode7 = new TreeNode(null, 7, null);
        TreeNode treeNode8 = new TreeNode(treeNode6, 8, treeNode7);
        TreeNode treeNode9 = new TreeNode(null, 9, null);
        TreeNode treeNode3 = new TreeNode(treeNode9, 3, treeNode8);
        levelOrder3(treeNode3);
    }

    /**
     * 队列实现
     *
     * @param root
     */
    public static void levelOrder1(TreeNode root) {
        //生产FIFO队列
        Queue<TreeNode> queue = new LinkedList<>();
        //如果节点不为空，那么加入FIFO队列
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            //读取当前层的元素的个数
            int size = queue.size();
            //遍历当前层的每个节点
            for (int i = 0; i < size; i++) {
                //当前层前面的节点出队
                TreeNode cur = queue.poll();
                System.out.println(cur.getVal());
                //把下一层节点入队
                if (cur.getLeft() != null) {
                    queue.offer(cur.getLeft());
                }
                if (cur.getRight() != null) {
                    queue.offer(cur.getRight());
                }
            }
        }
    }

    /**
     * 栈实现
     *
     * @param root
     */
    public static void levelOrder2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) {
            stack.push(root);
        }
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            System.out.println(cur.getVal());
            if (cur.getRight() != null) {
                stack.push(cur.getRight());
            }
            if (cur.getLeft() != null) {
                stack.push(cur.getLeft());
            }
        }
    }

    /**
     * 两个list来实现
     *
     * @param root
     */
    public static void levelOrder3(TreeNode root) {
        //初始化当前层节点
        List<TreeNode> curLevel = new ArrayList<>();
        //root不为空的时候才加到list里面
        if (root != null) {
            curLevel.add(root);
        }
        while (!curLevel.isEmpty()) {
            //用来存放下一层的节点
            List<TreeNode> nextLevel = new ArrayList<>();
            //遍历当前层每一个节点
            for (TreeNode cur : curLevel) {
                System.out.println(cur.getVal());
                if (cur.getLeft() != null) {
                    nextLevel.add(cur.getLeft());
                }
                if (cur.getRight() != null) {
                    nextLevel.add(cur.getRight());
                }
            }
            curLevel = nextLevel;
        }
    }
}